package algorithm.leetcode.simple;

/*
 岛屿的周长
 给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/23
 */
public class Question463 {

    public static void main(String[] args) {
        int[][] grid = {{1}};
        Question463 question = new Question463();
        int perimeter = question.islandPerimeter(grid);
        System.out.println(perimeter);
    }

    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return dfs(grid, i, j);
                }
            }
        }
        return 0;
    }

    /**
     * 思路：岛屿周长 = 与网格边界 + 与水域边界
     */
    private int dfs(int[][] grid, int i, int j) {
        if (!(i >= 0 && i < grid.length && j >= 0 && j < grid[0].length)) {
            // 从一个岛屿方格走向网格边界，周长加 1
            return 1;
        }
        // 从一个岛屿方格走向水域方格，周长加 1
        if (grid[i][j] == 0) {
            return 1;
        }
        // 避免重复遍历
        if (grid[i][j] != 1) {
            return 0;
        }
        // 标记已访问
        grid[i][j] = 2;
        return dfs(grid, i - 1, j) + dfs(grid, i + 1, j) +
                dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
    }


}
